package com.bi.model.pojo;


import org.springframework.stereotype.Component;


@Component
public class BTree {
    private static final int MIN_DEGREE = 4; // 默认B树的度数为4
    private Node root;

    public BTree() {
        root = new Node(MIN_DEGREE);
    }

    public void insert(int key, String value) {
        root = insertRec(root, key, value);
    }

    private Node insertRec(Node node, int key, String value) {
        if (node.isLeaf()) {
            if (node.count == 2 * MIN_DEGREE - 1) {
                Node left = new Node(MIN_DEGREE);
                Node right = new Node(MIN_DEGREE);
                int mid = (2 * MIN_DEGREE - 1) / 2;

                int[] keys = node.keys;
                String[] values = node.values;
                for (int i = 0; i < mid; i++) {
                    left.keys[i] = keys[i];
                    left.values[i] = values[i];
                }
                for (int i = mid + 1; i < node.count; i++) {
                    right.keys[i - mid - 1] = keys[i];
                    right.values[i - mid - 1] = values[i];
                }

                left.count = mid;
                right.count = node.count - mid - 1;

                if (node.keys[mid] < key) {
                    left.children[left.count] = node.children[left.count - 1];
                    right.children[0] = node.children[left.count];
                    left.children[left.count - 1] = null;
                    right.keys[0] = node.keys[mid];
                    right.values[0] = node.values[mid];
                    node.keys[mid] = key;
                    node.values[mid] = value;
                } else {
                    right.keys[0] = node.keys[mid];
                    node.keys[mid] = key;
                    left.children[left.count] = node.children[left.count - 1];
                    right.children[0] = node.children[left.count];
                }

                node.children = new Node[2 * MIN_DEGREE];
                node.children[0] = left;
                node.children[1] = right;
                node.count = 1;
                return node;
            } else {
                node.keys[node.count] = key;
                node.values[node.count] = value;
                node.count++;
                return node;
            }
        } else {
            int i = 0;
            while (i < node.count && key > node.keys[i]) {
                i++;
            }

            node.children[i] = insertRec(node.children[i], key, value);
            return balance(node);
        }
    }

    private Node balance(Node node) {
        if (node.count < MIN_DEGREE) {
            if (node.isLeaf()) {
                if (node.prev != null && node.prev.count > MIN_DEGREE - 1) {
                    node.prev.keys[node.prev.count] = node.keys[0];
                    node.prev.values[node.prev.count] = node.values[0];
                    node.prev.children[node.prev.count + 1] = node.children[0];
                    node.prev.count++;
                    node.keys[0] = node.prev.keys[node.prev.count - 1];
                    node.values[0] = node.prev.values[node.prev.count - 1];
                    node.prev.keys[node.prev.count - 1] = Integer.MAX_VALUE;
                    node.prev.values[node.prev.count - 1] = "" + Integer.MAX_VALUE;
                    node.children[0] = node.prev.children[node.prev.count - 1];
                    node.prev.children[node.prev.count - 1] = null;
                    node.prev.count--;
                    return node.prev;
                } else if (node.next != null && node.next.count > MIN_DEGREE - 1) {
                    node.keys[0] = node.next.keys[0];
                    node.values[0] = node.next.values[0];
                    node.children[1] = node.next.children[0];
                    node.next.keys[0] = node.next.keys[1];
                    node.next.values[0] = node.next.values[1];
                    node.next.children[0] = node.next.children[1];
                    node.count++;
                    node.next.count--;
                    return node;
                } else {
                    if (node.prev != null) node.prev.next = node.next;
                    if (node.next != null) node.next.prev = node.prev;
                    if (node.prev != null) return node.prev;
                    else return node.next;
                }
            } else {
                // Non-leaf nodes
                if (node.children[0] != null && node.children[0].count > MIN_DEGREE - 1) {
                    // Steal from first child
                    node.keys[node.count] = node.children[0].keys[0];
                    node.values[node.count] = node.children[0].values[0];
                    node.children[node.count + 1] = node.children[0].children[0];
                    node.count++;
                    node.children[0].keys[0] = Integer.MAX_VALUE;
                    node.children[0].values[0] = "" + Integer.MAX_VALUE;
                    node.children[0].children[0] = null;
                    node.children[0].count--;
                    return node;
                } else if (node.children[node.count] != null && node.children[node.count].count > MIN_DEGREE - 1) {
                    // Steal from last child
                    node.keys[node.count - 1] = node.children[node.count].keys[0];
                    node.values[node.count - 1] = node.children[node.count].values[0];
                    node.children[node.count].keys[0] = Integer.MAX_VALUE;
                    node.children[node.count].values[0] = "" + Integer.MAX_VALUE;
                    node.children[node.count].children[0] = null;
                    node.children[node.count].count--;
                    return node;
                } else {
                    // Merge with sibling
                    if (node.prev != null) {
                        node.prev.children[node.prev.count + 1] = node.children[0];
                        node.children[0].prev = node.prev;
                        node.prev.keys[node.prev.count] = node.keys[0];
                        node.prev.values[node.prev.count] = node.values[0];
                        node.prev.children[node.prev.count] = node.children[1];
                        node.prev.children[node.prev.count].prev = node.prev;
                        node.prev.count++;
                        node.prev.count--;
                        node.children[0] = node.children[1];
                        node.children[1] = null;
                        node.keys[0] = node.prev.keys[node.prev.count - 1];
                        node.values[0] = node.prev.values[node.prev.count - 1];
                        node.prev.keys[node.prev.count - 1] = Integer.MAX_VALUE;
                        node.prev.values[node.prev.count - 1] = "" + Integer.MAX_VALUE;
                        node.prev.count--;
                        return node.prev;
                    } else {
                        node.next.keys[0] = node.keys[0];
                        node.next.values[0] = node.values[0];
                        node.next.children[0] = node.children[0];
                        node.next.children[0].prev = node.next;
                        node.next.count++;
                        node.count--;
                        node.children[0] = node.children[1];
                        node.children[1] = null;
                        node.keys[0] = node.next.keys[0];
                        node.values[0] = node.next.values[0];
                        node.next.keys[0] = Integer.MAX_VALUE;
                        node.next.values[0] = "" + Integer.MAX_VALUE;
                        node.next.count--;
                        return node;
                    }
                }
            }
        }
        return node;
    }

    public Node deleteRec(Node root, int key) {
        if (root == null) {
            return root;
        }

        if (root.isLeaf()) {
            return deleteLeaf(root, key);
        } else {
            int i = 0;
            while (i < root.count && key > root.keys[i]) {
                i++;
            }

            if (i < root.count && root.keys[i] == key) {
                root.keys[i] = deleteRec(root.children[i], Integer.MAX_VALUE).keys[0];
                root.values[i] = deleteRec(root.children[i], Integer.MAX_VALUE).values[0];
            } else {
                root.children[i] = deleteRec(root.children[i], key);
            }
        }

        return balance(root);
    }

    private Node deleteLeaf(Node node, int key) {
        int i;
        for (i = 0; i < node.count; i++) {
            if (node.keys[i] == key) {
                break;
            }
        }

        for (int j = i; j < node.count - 1; j++) {
            node.keys[j] = node.keys[j + 1];
            node.values[j] = node.values[j + 1];
            node.children[j] = node.children[j + 1];
        }

        node.count--;
        node.children[node.count] = null;

        return balance(node);
    }

    public class Node {
        int count;
        int[] keys;
        String[] values;
        Node[] children;
        Node prev, next;

        public Node(int minDegree) {
            keys = new int[2 * minDegree - 1];
            values = new String[2 * minDegree - 1];
            children = new Node[2 * minDegree];
            count = 0;
        }

        public boolean isLeaf() {
            return children[0] == null;
        }
    }

    public void inorder() {
        inorderRec(root);
    }

    public String find(int key) {
        return find(root, key);
    }

    private String find(Node node, Integer key) {
        if (key != null) {
            for (int i = 0; i < node.count; i++) {
                if (node.keys[i] == key) {
                    return node.values[i];
                }
                find(node.children[i], key);
//                System.out.print(node.keys[i] + " ");
            }
            find(node.children[node.count], key);
        }
        return null;
    }

    private void inorderRec(Node node) {
        if (node != null) {
            for (int i = 0; i < node.count; i++) {
                inorderRec(node.children[i]);
                System.out.print(node.keys[i] + " ");
            }
            inorderRec(node.children[node.count]);
        }
    }

    public void delete(int key) {
        root = deleteRec(root, key);
    }

   /* public static void main(String[] args) {
        BTree bTree = new BTree();
        bTree.insert(50);
        bTree.insert(30);
        bTree.insert(70);
        bTree.insert(10);
        bTree.insert(60);
        bTree.insert(40);
        bTree.insert(80);
        bTree.insert(20);
        bTree.insert(90);
        bTree.insert(100);


        System.out.println("Inorder traversal of the constructed B-Tree:");
        bTree.inorder();
    }*/
}